package com.njupt.Tree;



import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/11/23 20:16
 * @Description: 111、二叉树的最小深度
 * @Version: 1.0
 */


public class MinDepth {

    /**
     * 中序遍历 非递归法
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        Deque<TreeNode> stack1 = new LinkedList<>();
        Deque<Integer> stack2 = new LinkedList<>();

        if(root == null) return 0;
        int currentDepth = 0;
        int minDepth = Integer.MAX_VALUE;
        TreeNode cur = root;

        while(cur != null || !stack1.isEmpty()){
            if(cur != null){
                stack1.push(cur);
                stack2.push(++currentDepth);
                cur = cur.left;
            }else {
                cur =  stack1.pop();
                currentDepth = stack2.pop();
                if(cur.left == null && cur.right == null){
                    if(currentDepth<minDepth){
                        minDepth = currentDepth;
                    }
                }
                cur = cur.right;
            }
        }
        return minDepth;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        MinDepth test = new MinDepth();
        System.out.println(test.minDepth(root));
    }
}
